ICPC Live Archive/4794 - Sharing Chocolate/4794.cpp

   1 #include <algorithm>
   2 #include <iostream>
   3 #include <iterator>
   4 #include <sstream>
   5 #include <fstream>
   6 #include <cassert>
   7 #include <climits>
   8 #include <cstdlib>
   9 #include <cstring>
  10 #include <string>
  11 #include <cstdio>
  12 #include <vector>
  13 #include <cmath>
  14 #include <queue>
  15 #include <deque>
  16 #include <stack>
  17 #include <list>
  18 #include <map>
  19 #include <set>
  20
  21 using namespace std;
  22
  23 template <class T> string toStr(const T &x){
  24 stringstream s; s << x; return s.str();
  25 }
  26
  27 template <class T> int toInt(const T &x){
  28 stringstream s; s << x; int r; s >> r; return r;
  29 }
  30
  31 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  32 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  33 #define D(x) cout << #x " = " << (x) << endl
  34
  35 const double EPS = 1e-9;
  36 int cmp(double x, double y, double tol = EPS){
  37   return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  38 }
  39
  40 const int MAXN = 15;
  41 const int MAXR = 105;
  42 const int MAXS = MAXR * MAXR;
  43
  44 int a[MAXN];
  45 int sum[1 << MAXN];
  46 int popcount[1 << MAXN];
  47 int memo[MAXR][1 << MAXN];
  48 vector<int> masks[MAXS];
  49
  50 int n;
  51
  52 bool f(int r, int c, int mask){
  53   //printf("f(r=%d, c=%d, mask=%x, sum[mask]=%d)\n", r, c, mask, sum[mask]);
  54   if (sum[mask] != r * c) return false;
  55
  56   // r * c == sum[mask]
  57   if (popcount[mask] == 1) return true;
  58
  59
  60   if (memo[r][mask] != -1) return memo[r][mask];
  61
  62   for (int i=1; i<r; ++i){
  63     int rleft = i, rright = r - i;
  64     //printf("rleft = %d, rright = %d\n", rleft, rright);
  65
  66     const vector<int> &optionsleft = masks[ rleft * c ];
  67     for (int k = 0; k < optionsleft.size(); ++k){
  68       int lsubset = optionsleft[k];
  69       if (~mask & lsubset) continue;
  70       int rsubset = mask & ~lsubset;
  71
  72       //printf("lsubset = %X, rsubset = %X\n", lsubset, rsubset);
  73       assert((lsubset | rsubset) == mask);
  74       assert((lsubset & rsubset) == 0);
  75       assert(sum[lsubset] == rleft * c);
  76
  77       if (sum[rsubset] == rright * c){
  78         bool maybe = f(rleft, c, lsubset) && f(rright, c, rsubset);
  79         if (maybe){
  80           memo[r][mask] = memo[c][mask] = 1;
  81           return 1;
  82         }
  83       }
  84     }
  85   }
  86
  87   for (int j=1; j<c; ++j){
  88     int cleft = j, cright = c - j;
  89     const vector<int> &optionsleft = masks[ cleft * r ];
  90     for (int k = 0; k < optionsleft.size(); ++k){
  91       int lsubset = optionsleft[k];
  92       if (~mask & lsubset) continue;
  93       int rsubset = mask & ~lsubset;
  94       assert((lsubset | rsubset) == mask);
  95       assert((lsubset & rsubset) == 0);
  96       assert(sum[lsubset] == cleft * r);
  97
  98       if (sum[rsubset] == cright * r){
  99         bool maybe = f(r, cleft, lsubset) && f(r, cright, rsubset);
 100         if (maybe){
 101           memo[r][mask] = memo[c][mask] = 1;
 102           return 1;
 103         }
 104       }
 105     }
 106   }
 107
 108
 109
 110   memo[r][mask] = memo[c][mask] = 0;
 111   return 0;
 112 }
 113
 114 int main(){
 115   int Case = 0;
 116   while (scanf("%d", &n) == 1){
 117     if (n == 0) break;
 118     printf("Case %d: ", ++Case);
 119
 120     int r, c;
 121     scanf("%d %d", &r, &c);
 122     for (int i = 0; i < n; ++i){
 123       scanf("%d", &a[i]);
 124     }
 125
 126     for (int i = 0; i <= r * c; ++i){
 127       masks[i].clear();
 128     }
 129
 130     for (int mask = 0; mask < (1 << n); ++mask){
 131       sum[mask] = popcount[mask] = 0;
 132       for (int k = 0; k < n; ++k){
 133         if (mask & (1 << k)){
 134           sum[mask] += a[k];
 135           popcount[mask]++;
 136         }
 137       }
 138
 139       masks[sum[mask]].push_back(mask);
 140
 141       for (int i = 0; i < MAXR; ++i){
 142         memo[i][mask] = -1;
 143       }
 144     }
 145
 146     // for (int mask = 0; mask < (1 << n); ++mask){
 147     //   printf("Mask = %X\n", mask);
 148     //   printf("    popcount = %d\n", popcount[mask]);
 149     //   printf("    sum = %d\n", sum[mask]);
 150     // }
 151
 152     bool ans = f(r, c, (1 << n) - 1);
 153     printf("%s\n", ans ? "Yes" : "No");
 154   }
 155   return 0;
 156 }